This invention is concerned with Finite State Automata (FSA's) that are responsive to a stream of input code data. An FSA is a device which is said to exist in a single state at any given instant, and makes transition, or "steps," from state to state under control of tables stored within the FSA as the input codes are received.
In many applications of FSA's, such as in text searching, when the FSA is in a given state, there may or may not be a multiplicity of possible success states to which transitions are possible in response to respective sought values of the input code, as well as default states, to which transition is made in response to other input code values. In general, the data stored within the control table associated with the given state have been required to identify all such possible transition states, and the input code values which would cause a transition to each such state.
As a result of these requirements, the amount of memory hardware for control table storage is of concern in any FSA implementation. The exact method of implementation can affect the amount of memory required.
One possible scheme is described in the article by R. H. Bullen, Jr. and J. K. Millen entitled "Microtext--The design of a microprogrammed finite state search machine for full-text retrieval," AFIPS Conference Proceeding, Fall Joint Computer Conference, 1972, pp. 479-488. Basically that scheme involves a table of decision data stored for each state. Each table entry includes a particular code element value against which an incoming code element is compared, plus search displacement increments, and a next state address. As an input code element is compared against the stored request or query code value, depending upon whether they are equal, or which is greater, the FSA can take one of three actions: go to the next state, or continue to search the present state table in either the plus or minus direction until a stored query code value does match the incoming code value, using the displacement increments to simplify the search.
That prior art system illustrates the ability of the finite state approach to provide flexible sequential action of the search mechanism in searching a character string, for example. If the search request includes many query words which are to be sought simultaneously, a specific initial task of the FSA is clearly to search the input string for every character that is an initial character of one of the query words. Hence, an initial state of the FSA is typically one in which the associated section of the control table contains a distinct entry for each such initial character. Each entry identifies the particular initial character, and also identifies the next state to which the FSA is to make transition if and when that initial character is found in the input data stream.
When under control of the table section for such a multiple exit state, the FSA described in the Bullen et al article effectively compares the current input character of the data stream sequentially with each of the "significant," or query, characters stored in the respective table entries associated with the current state. If one of those entries yields a match, the FSA makes transition to the success state designated in that table entry. The FSA thus comes under control of the table section associated with that next state. That table section will identify the respective second characters of all query words whose initial character has just been found. If there is only one such query word, the table section typically has only a single significant entry.
Thus, a simple change of state can radically alter the function of the basic search mechanism. In one state that mechanism searches the input data stream for a set of many designated characters that are initial characters of different query words. In the next state, depending upon the result of the first search, it may search for a single designated character that is the second character of a selected one of those query words.
However, the approach described in the cited article is time consuming due to the multiple tries against each state table, and is expensive of memory due to the multiple entry table associated with each state.
The subject of this disclosure provides a more practical solution to the multiple exit state requirement, making the FSA concept much more usable to a wider range of applications.